package arithmetic.LeetCode;

/**
 * https://leetcode-cn.com/problems/search-rotate-array-lcci/solution/xuan-zhuan-shu-zu-cong-yi-dao-nan-ge-ge-dcv7a/
 * 旋转数组问题
 * https://leetcode-cn.com/problems/search-rotate-array-lcci/comments/
 *
 * 搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
 *
 * 示例1:
 *
 *  输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 *  输出: 8（元素5在该数组中的索引）
 *
 * 示例2:
 *
 *  输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 *  输出：-1 （没有找到）
 * 提示:
 *
 * arr 长度范围在[1, 1000000]之间
 *
 *
 */
public class RorateArray {

    public static int search(int[] arr, int target) {
        int left =0;
        int right=arr.length-1;
        while(left <= right){
            int mid = (left + right)/2;
            if (arr[mid] == target){
                return mid;
            }
            if(arr[left]<=arr[mid]){
                if( arr[left]==target){
                    return left;
                }
                if(arr[mid]>target && arr[left]<target){
                    right = mid -1;
                }else{
                    left = mid +1;
                }
            }else{
                if( arr[right]==target){
                    return right;
                }
                if(arr[mid]<target && arr[right]>target){
                    left = mid +1;
                }else{
                    right = mid -1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,1,1,1,2,1,1,1};


        System.out.println(search(arr,2));
        // 主要问题:重复数字返回最小序号
        int[] arr2 = {5,5,5,1,2,3,4,5};
        System.out.println(search(arr2,5));

        // 输出：14   预期结果：13
        int[] arr3 = {21, 21, -21, -20, -17, -8, -6, -2, -2, -1, 0, 2, 3, 4, 4, 6, 11, 13, 14, 16, 17, 18, 20};
        System.out.println(search(arr3,4));

    }
}
